<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <meta http-equiv="X-UA-Compatible" content="ie=edge">
  <title>时间空间复杂度</title>
  <style>
    p, li {
      line-height: 40px
    }
    span {
      color: red
    }
  </style>
</head>
<body>
  <h2>通过JS实例讲解时间复杂度与空间复杂度</h2>
  <h3>算法的时间复杂度就是说一个算法的执行时间根据数据规模(<span>通常指n变量</span>)增长的一个趋势</h3>
  <ul>
    <li>
      <div>T(n) = O(f(n))</div>
      <div>S(n) = O(f(n))</div>
      <div>大O表示法，T代表的是算法需要执行的总时间</div>
      <div>S表示算法需要的总空间</div>
      <div>n表示的是代码执行的总次数, f(n)是时间复杂度的一个表达式</div>
    </li>
    <li>
      <pre>
          function go (n) {
            var item = 0                           // 1
            for (var i = 0; i < n; i++) {          // n
              for (var j = 0; j < n; j++) {        // n * n
                item = item + i + j                // n * n
              }
            }
            return item                            // 1
          }
      </pre>
      <div>
          上述代码总的执行次数是 1 + n + n * n + n * n + 1 = 2n<sup>2</sup> + n + 2
      </div>
      <div>取最高阶，时间复杂度是O(n<sup>2</sup>)</div>
    </li>
    <li>
      <h3>对数阶乘</h3>
      <pre>
          function go5(n) {
            var i = 1
            while (i <= n) {
              i = i * 10
            }
          }
          
          // i = 1
          // i = 1 * 10
          // i = 1 * 10 * 10
          // i = 1 * 10 * 10 * 10 
          // .....
          
          // question: 执行了多少次？
          // 设为 Y
          // n = 10 ^ y
          // y = lgn
          // 即时间复杂度时lgn
      </pre>
    </li>
  </ul>

  <h3>算法的空间复杂度</h3>
  <ul>
    <li>
      时间复杂度是代码执行时间的趋势，同理，空间复杂度即使指的内存的趋势
    </li>
  </ul>


  <script src="./index.js"></script>
</body>
</html>